//https://leetcode.cn/problems/operations-on-tree/description/?envType=daily-question&envId=2023-09-23


class LockingTree {
public:
    vector<vector<int>> tree;
    vector<int> lockflag;
    vector<int> parent;
    LockingTree(vector<int>& parent) {
        this->parent=parent;
        this->tree.resize(parent.size());
        this->lockflag.resize(parent.size());
        for(auto& lf:lockflag){
            lf=-1;
        }
        for(int i=1;i<parent.size();i++){
            this->tree[parent[i]].push_back(i);
        }
    }
    
    bool lock(int num, int user) {
        if(lockflag[num]==-1){
            lockflag[num]=user;
            return true;
        }
        return false;
    }
    
    bool unlock(int num, int user) {
        if(lockflag[num]==user){
            lockflag[num]=-1;
            return true;
        }
        return false;
    }
    
    bool upgrade(int num, int user) {
        bool childflag=false;
        if(lockflag[num]==-1){
            
            for(int pa=this->parent[num];pa!=-1;pa=this->parent[pa]){
                if(lockflag[pa]!=-1)return false;
            }
            queue<vector<int>> myQueue;
            myQueue.push(this->tree[num]);
            while(!myQueue.empty()){
                vector<int> vec=myQueue.front();
                myQueue.pop();
                for(auto& a:vec){
                    if(lockflag[a]!=-1){
                        childflag=true;
                        lockflag[a]=-1;
                    }
                    myQueue.push(this->tree[a]);   
                }
            }
            if(childflag) lockflag[num]=user;
            return childflag;
        }
        return false;
    }
};